// 2025/10/30
// 最小基因变化

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        int m = startGene.size(), n = bank.size();
        vector<vector<int>> adj(n);
        int endIndex = -1;
        for(int i = 0; i < n; i++)
        {
            if(endGene == bank[i])
                endIndex = i;
            for(int j = i + 1; j < n; j++)
            {
                int count = 0;
                for(int k = 0; k < m; k++)
                {
                    if(bank[i][k] != bank[j][k])
                        count++;
                    if(count > 1)
                        break;
                }
                if(count == 1)
                {
                    adj[i].emplace_back(j);
                    adj[j].emplace_back(i);
                }
            }
        }
        if(endIndex == -1)
            return -1;

        queue<int> q;
        vector<bool> isVisited(n, false);
        for(int i = 0; i < n; i++)
        {
            int count = 0;
            for(int j = 0; j < m; j++)
            {
                if(bank[i][j] != startGene[j])
                    count++;
                if(count > 1)
                    break;
            }
            if(count == 1)
            {
                q.emplace(i);
                isVisited[i] = true;
            }
        }

        int step = 1;
        while(!q.empty())
        {
            int sz = q.size();
            while(sz--)
            {
                int cur = q.front();
                q.pop();
                if(cur == endIndex)
                    return step;
                for(auto& pos : adj[cur])
                {
                    if(!isVisited[pos])
                    {
                        q.emplace(pos);
                        isVisited[pos] = true;
                    }
                }
            }
            step++;
        }
        return -1;
    }
};